#pragma once
#include <iostream>
#include <vector>

namespace me
{
    enum class status
    {
        EMPTY,
        EXIST,
        DELETE
    };

    template <typename K, typename V>
    struct hashNode
    {
        std::pair<K, V> _kv;
        status _state;
    };

    template <typename K, typename V, typename K2I>
    class hashTable
    {
        inline unsigned long __stl_next_prime(unsigned long n)
        {
        	// Note: assumes long is at least 32 bits.
        	static const int __stl_num_primes = 28;
        	static const unsigned long __stl_prime_list[__stl_num_primes] = {
        		53,			97,			193,		389,       769,
        		1543,		3079,		6151,		12289,	   24593,
        		49157,      98317,		196613,		393241,	   786433,
        		1572869,    3145739,	6291469,	12582917,  25165843,
        		50331653,   100663319,	201326611,  402653189, 805306457,
        		1610612741, 3221225473, 4294967291
        	};
        	const unsigned long* first = __stl_prime_list;
        	const unsigned long* last = __stl_prime_list + __stl_num_primes;
        	const unsigned long* pos = lower_bound(first, last, n);
        	return pos == last ? *(last - 1) : *pos;
        }
        using node = hashNode<K,V>;
    public:
        hashTable(int size = 0):_table(__stl_next_prime(size)), _n(0) {}

        bool insert(const std::pair<K, V>& kv)
        {
            // 计算负载因子，如果超过0.7则进行扩容
            if(10 * _n / _table.size() > 7) {
                hashTable<K, V, K2I> newhash(_table.size() + 1);

                for(auto& e : _table) {
                    if(e._state == status::EXIST) {
                        newhash.insert(e._kv);
                    }
                }

                _table.swap(newhash._table);
            }

            // 根据哈希函数，计算映射位置
            int h1 = _k2i(kv.first) % _table.size();
            int h2 = h1;
            int i = 1;
            while(_table[h2]._state != status::EMPTY) {
                // 重复值不插入
                if(_table[h2]._state == status::EXIST && _table[h2]._kv.first == kv.first) {
                    return false;
                }
                // 线性探测
                h2 = (h1 + i) % _table.size();
                i++;
            }

            // h2即为最终位置
            _table[h2]._kv = kv;
            _table[h2]._state = status::EXIST;
            _n++;
            return true;
        }

        node* find(const K& key)
        {
            int h1 = _k2i(key) % _table.size();
            int h2 = h1;
            int i = 0;
            while(_table[h2]._state != status::EMPTY) {
                if(_table[h2]._state == status::EXIST 
                && _table[h2]._kv.first == key) {
                    return &_table[h2];
                }

                h2 = (h1 + i) % _table.size();
                i++;

                if(i > _table.size()) break;
            } 
            return nullptr;
        }

        bool erase(const K& key)
        {
            node* pos = find(key);
            if(pos) {
                pos->_state = status::DELETE;
                return true;
            }

            return false;
        }
    private:
        std::vector<node> _table;
        size_t _n;
        K2I _k2i;
    };
}